|
In mathematics, Neville's algorithm is an algorithm used for polynomial interpolation that was derived by the mathematician Eric Harold Neville. Given ''n'' + 1 points, there is a unique polynomial of degree ''≤ n'' which goes through the given points. Neville's algorithm evaluates this polynomial. Neville's algorithm is based on the Newton form of the interpolating polynomial and the recursion relation for the divided differences. It is similar to Aitken's algorithm (named after Alexander Aitken), which is nowadays not used. ==The algorithm== Given a set of ''n''+1 data points (''x''''i'', ''y''''i'') where no two ''x''''i'' are the same, the interpolating polynomial is the polynomial ''p'' of degree at most ''n'' with the property :''p''(''x''''i'') = ''y''''i'' for all ''i'' = 0,…,''n'' This polynomial exists and it is unique. Neville's algorithm evaluates the polynomial at some point ''x''. Let ''p''''i'',''j'' denote the polynomial of degree ''j'' − ''i'' which goes through the points (''x''''k'', ''y''''k'') for ''k'' = ''i'', ''i'' + 1, …, ''j''. The ''p''''i'',''j'' satisfy the recurrence relation :(x) = \frac(x)}, \, || |} This recurrence can calculate ''p''0,''n''(''x''), which is the value being sought. This is Neville's algorithm. For instance, for ''n'' = 4, one can use the recurrence to fill the triangular tableau below from the left to the right. :(x) \, |- | || || |- | || || || |- | || || || || style="border: 1px solid;" | |- | || || || |- | || || |- | || |- | |} This process yields ''p''0,4(''x''), the value of the polynomial going through the ''n'' + 1 data points (''x''''i'', ''y''''i'') at the point ''x''. This algorithm needs O(''n''2) floating point operations. The derivative of the polynomial can be obtained in the same manner, i.e: :(x) = \frac(x) + (x-x_i)p'_(x) + p_(x)}, \, || |} 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Neville's algorithm」の詳細全文を読む スポンサード リンク
|